//【Day13】LeetCode力扣刷题[面试题 17.19. 消失的两个数字][70.爬楼梯][746. 使用最小花费爬楼梯]



/*[面试题 17.19. 消失的两个数字]
题目描述：

给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？
以任意顺序返回这两个数字均可。
/
示例 1:
输入: [1]
输出: [2,3]
/
示例 2:
输入: [2,3]
输出: [1,4]
/
提示：

nums.length <= 30000
解题思路：
利用异或运算符解答：
0 ^ a = a;
当一个数重复异或会抵消：
a ^ b ^ a = b;
那么我们将1-N个数异或，再将nums[]中的数异或，就得到了消失的两个数的异或值。
之后将出现的数分为 二进制表示的第 1 位为 0 的数，和 二进制表示的第 1位为 1 的数。
将他们异或，消除重复，就分别得到了两个消失的数。
————————————————
版权声明：本文为CSDN博主「.29.」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/ebb29bbe/article/details/127046589*/



class Solution {
    public int[] missingTwo(int[] nums) {
        int n = nums.length+2;           //nums[]长度+2才是1到N的个数
        int diff = 0;                    //准备获取消失两个数的异或值
        
        //先对1-N进行异或处理
        for(int i = 1;i <= n; ++i)  diff ^= i;

        //再对消失了两个数的nums[]进行异或处理
        //被异或过的数再次异或会抵消，即a^a^b = b
        //还有0^a = a,所以diff初始值为0；
        //这么一来，现在的diff相当于疑惑了两个消失的数:a^b
        for(int num : nums) diff ^= num;

        int lsb = (diff & -diff);//取出diff的二进制表示中最低位那个1
        int T1 = 0,T2 = 0;

        //利用lsb将1-N中出现的数分为两类，出现两次的一类，出现一次的（消失的数）一类
        //再将它们全部异或起来，抵消出现两次的，剩下消失的两个数
        for(int i = 1;i <= n;++i){
            if((i & lsb) != 0){
                T1 ^= i;
            }else{
                T2 ^= i;
            }
        }

        for(int num : nums){
            if((num & lsb) != 0){
                T1 ^= num;
            }else{
                T2 ^= num;
            }
        }

        return new int[]{T1,T2};
    }
}







/*[70.爬楼梯]
题目描述：

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例 1：
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
①1 阶 + 1 阶
② 2 阶
/
示例 2：
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
①1 阶 + 1 阶 + 1 阶
② 1 阶 + 2 阶
③ 2 阶 + 1 阶
提示：
1 <= n <= 45

解题思路:
动态规划：
每多一阶台阶，上台阶的方法都是前两阶上台阶方法数量的和；
————————————————
版权声明：本文为CSDN博主「.29.」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/ebb29bbe/article/details/127046589*/



class Solution {
    public int climbStairs(int n) {
        int a = 0,b = 0,sum = 1;
        for(int i = 0;i < n;++i){
            a = b;
            b = sum;
            sum = a+b;
        }
        return sum;
    }
}








/*[746. 使用最小花费爬楼梯]
题目描述：

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为0或下标为1的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
/
示例 1：
输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。

支付 15 ，向上爬两个台阶，到达楼梯顶部。
总花费为 15 。
/
示例 2：
输入：cost = [1,100,1,1,1,100,1,1,100,1]
输出：6
解释：你将从下标为 0 的台阶开始。

支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。

支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。

支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。

支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。

支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。

支付 1 ，向上爬一个台阶，到达楼梯顶部。
总花费为 6 。

解题思路：
与上一道爬楼梯的解题思路一致，只是不需要记录爬楼梯的方法，而是记录前两阶价格中，更优惠的方案
————————————————
版权声明：本文为CSDN博主「.29.」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/ebb29bbe/article/details/127046589*/


class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int a = 0,b = 0,curr = 0;
        //依旧是动态规划
        //与爬楼梯问题几乎一样，只不过是方式换成了最低消费
        for(int i = 2;i <= cost.length;++i){
            //至于前两阶相关，选价格较低的方案
            curr = Math.min(a+cost[i-2],b+cost[i-1]);
            a = b;
            b = curr;
        }
        return curr;
    }
}
